package algotithm.weekendrace.leetcode230.test2;

import java.util.HashSet;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/28-10:26
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] baseCosts = {1,7};
//        int[] toppingCosts = {3,4};
//        int target = 10;
        int[] baseCosts = {2,3};
        int[] toppingCosts = {4,5,100};
        int target = 18;
        int closestCost = solution.closestCost(baseCosts, toppingCosts, target);
        System.out.println(closestCost);
    }

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int n = baseCosts.length, m = toppingCosts.length, M = (int) Math.pow(3, m);
        HashSet<Integer> mSet = new HashSet();
        for(int st = 0; st < M; st++) {
            int tmp = st, cost = 0, ind = 0;
            while(tmp > 0) {
                cost += (tmp % 3) * toppingCosts[ind++];
                tmp /= 3;
            }
            mSet.add(cost);
        }
        int res = -1, min = 2000000;
        for(int i : mSet) {
            for(int j : baseCosts) {
                if(Math.abs(j + i - target) < min || target - j - i == min) {
                    res = j + i;
                    min = Math.abs(j + i - target);
                }
            }
        }
        return res;
    }


}
